/*
 *https://leetcode.cn/problems/minimum-limit-of-balls-in-a-bag/
 *1760. 袋子里最少数目的球
 *medium 吴朝泽 2024.9.12
 *二分查找
将问题转换为在 maxOperations 次的约束下，能否使单个袋子的球的个数最大值不超过 mid 。
左边界从 1 开始，右边界查找 vector 数组中第一个最大值的位置，可以优化算法不先排序。
遍历 vector 数组，(nums[i] - 1) / mid 计算的是将 nums[i] 分割成不超过 mid 大小的块所需的操作数，
减去 1 是为了确保在计算块数时考虑了所有完整块。
count 如果小于题目给的最大操作次数，可推断出是 mid 偏大了，故修改右边界；反之修改左边界。
*/


class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int n = nums.size();
        int l = 1, r = *max_element(nums.begin(),nums.end()); //直接查找最大元素所在的位置
        while(l <= r)
        {
            int mid = (l + r) / 2;
            long long count = 0;
            for(int i = 0; i < n; ++i)  count += (nums[i] - 1) / mid;
            if(count <= maxOperations)  r = mid - 1;
            else   l = mid + 1;     
        }
        return l;
        //为什么是返回 l 而不是 r ？
        //l 和 r 相交，l 将会是第一个不满足条件的块大小，而 r 是最后一个满足条件的块大小。
        //这是因为 l 是最后一次被更新的值，是符合条件的最小块大小，
        //而 r 只是一个过渡值，它最后已经不再满足条件。
    }
};
